
import java.util.*;
/**
 * 
 * 
 * 数字字符串转化成IP地址
 * 
 * 
 * 描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 
0
≤
n
≤
12
0≤n≤12
要求：空间复杂度 
O
(
n
!
)
O(n!),时间复杂度 
O
(
n
!
)
O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。
 */
public class 数字字符串转化成IP地址 {
    
    public static void main(String[] args) {
        
        restoreIpAddresses("25525522135").forEach(System.out::println);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    public static ArrayList<String> restoreIpAddresses (String s) {
        // write code here

        if(null==s || s.isEmpty() || s.length() > 12 || s.length() < 4) return resultList;
        
        
        backtrack(resultList, tempStr, s, 0, 0);

        return resultList;
    }

    static ArrayList<String> resultList = new ArrayList<>();
    static StringBuilder tempStr  =  new StringBuilder();

    private static void backtrack(ArrayList<String> result, StringBuilder current, String s, int start, int count) {
        if (count > 4) {
            return;
        }
        if (count == 4 && start == s.length()) {
            result.add(current.toString());
            return;
        }
        for (int i = start; i < start + 3 && i < s.length(); i++) {
            String part = s.substring(start, i + 1);
            if (isValidPart(part)) {
                int len = current.length();
                if (count > 0) {
                    current.append(".");
                }
                current.append(part);
                backtrack(result, current, s, i + 1, count + 1);
                current.delete(len, current.length());
            }
        }
    }

    private static boolean isValidPart(String part) {
        if (part.length() > 3 || part.length() == 0 || (part.length() > 1 && part.charAt(0) == '0')) {
            return false;
        }
        int num = Integer.parseInt(part);
        return num >= 0 && num <= 255;
    }
}